import java.util.Arrays;

public class MinimumTimeRequired {
    int[] kid;
    int ans = Integer.MAX_VALUE;

    public int minimumTimeRequired1(int[] jobs, int k) {
        kid = new int[jobs.length];
        process(jobs, 0, k);
        return ans;
    }

    public void process(int[] cookies, int i, int k) {
        if (i == cookies.length) {
            int max = Integer.MIN_VALUE;
            for (int j : kid) {
                max = Math.max(max, j);
            }
            ans = Math.min(ans, max);
            return;
        }
        for (int j = 0; j < k; j++) {
            int temp = kid[j];
            kid[j] += cookies[i];
            process(cookies, i + 1, k);
            kid[j] = temp;
        }
    }

    public int minimumTimeRequired(int[] jobs, int k) {
        Arrays.sort(jobs);
        int l = Integer.MIN_VALUE;
        int r = 0;
        int n = jobs.length;
        kid = new int[k];
        for (int i = 0; i < n; i++) {
            r += jobs[i];
            l = Math.max(l, jobs[i]);
        }
        while (l < r) {
            int mid = l + (r - l) / 2;
            if (check(jobs, mid, 0)) {
                r = mid;
            } else l = mid + 1;
            kid = new int[k];
        }
        return l;
    }

    public boolean check(int[] jobs, int target, int i) {
        if (i == jobs.length) {
            return true;
        }
        for (int j = 0; j < kid.length; j++) {
            if (kid[j] + jobs[i] <= target) {
                kid[j] += jobs[i];
                if (check(jobs, target, i + 1)) return true;
                kid[j] -= jobs[i];
            }
            if (kid[j] + jobs[i] == target || kid[j] == 0) break;
        }
        return false;
    }
}
